﻿// 反转插入排序  INSERTION.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
/*
https://algospot.com/judge/problem/read/INSERTION
问题

插入排序是一种著名的排序算法，它通过维护已排序的子数组，并将新元素插入到该数组中来进行排序。下面是对给定整数数组A进行插入排序的实现：

void insertionSort(vector<int>& A) {
for(int i = 0; i < A.size(); ++i) {
// 将A[i]插入到A[0..i-1]
int j = i;
while(j > 0 && A[j-1] > A[j]) {
// 不变式a: A[j+1..i]的所有元素都大于A[j]。
// 不变式b: 在去掉A[j]之外的A[0..i]区间内是有序的。
swap(A[j-1], A[j]);
--j;
}
}
}

插入排序在A[0..i-1]排好序的情况下，将A[i]向左移动一个位置，直到找到适当的位置。例如，对于A={5,1,4,3,2}，插入排序如下进行：

A	备注
5 1 4 3 2	初始状态
1 5 4 3 2	将1向左移动1个位置
1 4 5 3 2	将4向左移动1个位置
1 3 4 5 2	将3向左移动2个位置
1 2 3 4 5	将2向左移动3个位置

对包含从1到N的自然数的长度为N的序列A[]进行插入排序。虽然原始序列是未知的，但在过程中我们知道每个元素向左移动了多少个位置。例如，在上述示例中，每个位置上的值表示该位置上的元素移动了几个单元格，结果为{0,1,1,2,3}。现在请编写一个程序来找出原始序列。

输入
输入的第一行包含测试用例的数量C（1 <= C <= 50）。每个测试用例的第一行包含原数组的长度N（1 <= N <= 50000）。接下来的一行给出N个整数，表示每个位置上的元素移动的步数。A包含从1到N的整数，每个整数恰好出现一次。

由于输入量较大，请尽可能快地使用适当的输入函数。

输出
对于每个测试用例，请在一行上打印重构后的A[]。

示例输入
2
5
0 1 1 2 3
4
0 1 2 3

示例输出
5 1 4 3 2
4 3 2 1
*/
int main()
{
    std::cout << "Hello World!\n";
}

 